#include <iostream>

using namespace std;
using ll=long long;
const int N=1e5+10;

int a[N];
int n,p;
struct node{
	int l,r;
	int sum,add,mul;
}tr[N*4];

void pushup(int u)
{
	tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
//(a*b+c)*d+e
//a*b*d+c*d+e
void eval(int u,int add,int mul)
{
	tr[u].sum=((ll)tr[u].sum*mul+(ll)(tr[u].r-tr[u].l+1)*add)%p;
	tr[u].mul=(ll)tr[u].mul*mul%p;
	tr[u].add=((ll)tr[u].add*mul+add)%p;
}
void pushdown(int u)
{
	eval(u<<1,tr[u].add,tr[u].mul);
	eval(u<<1|1,tr[u].add,tr[u].mul);
	tr[u].add=0,tr[u].mul=1;
}
void build(int u,int l,int r)
{
	if(l==r)
		tr[u]={l,r,a[r],0,1};
	else{
		tr[u]={l,r,0,0,1};
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int l, int r,int add,int mul)
{
	if(tr[u].l>=l && tr[u].r<=r)
	{
		eval(u,add,mul);
	}
	else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)
		{
			modify(u<<1,l,r,add,mul);
		}
		if(r>mid)
		{
			modify(u<<1|1,l,r,add,mul);
		}
		pushup(u);
	}
}
int query(int u,int l,int r)
{
	if(tr[u].l>=l && tr[u].r<=r)
		return tr[u].sum;
	else{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		int sum=0;
		if(l<=mid)
			sum=query(u<<1,l,r);
		if(r>mid)
			sum=(sum+query(u<<1|1,l,r))%p;
		return sum;
	}
}
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}	
	
	build(1,1,n);
	int m;
	cin>>m;
	while(m--)
	{
		int op,t,g;
		scanf("%d%d%d",&op,&t,&g);
		if(op==1)
		{
			int c;
			scanf("%d",&c);
			modify(1,t,g,0,c);
		}
		else if(op==2)
		{
			int c;
			scanf("%d",&c);
			modify(1,t,g,c,1);
		}
		else{
			cout<<query(1,t,g)<<endl;
		}
	}
	return 0;
}
